package com.leetcode.动态规划;

import java.util.Arrays;

/**
 * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

 * @author LZF
 *
 */
public class L1143最长公共子序列 {
	public static void main(String[] args) {
		Solution1143 s1 = new Solution1143();
		int length = s1.longestCommonSubsequence("bsbininm", "jmjkbkjkv");
		System.out.println(length);
	}
}
class Solution1143 {
	//利用动态规划：二维dp
    public int longestCommonSubsequence(String text1, String text2) {
    	
    	//dp[i][j]：表示text1[0,i]和text2[0,j]的最长公共子序列
    	//上述表示中，text1[0,i]表示text1长度为i的前缀，text2[0,j]表示text2长度为j的前缀
    	
    	int m = text1.length();
    	int n = text2.length();
    	int[][] dp = new int[m + 1][n + 1];
    	/**
    	 * 递推公示：if(text1[i - 1] == text2[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1
    	 * 	      else  dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])
    	 * 初始化：i=0或j=0时 dp[i][j]=0
    	 */
    	for(int i = 1;i <= m;i++) {
    		for(int j = 1;j <= n;j++) {
    			dp[i][j] = text1.charAt(i - 1) == text2.charAt(j - 1) ? 
    					dp[i - 1][j - 1] + 1 : 
    						Math.max(dp[i - 1][j],dp[i][j - 1]);
    		}
    	}
  
    	return dp[m][n];
    }

}